package _08_DFS_BFS;

public class _547_省份数量 {

    public static void main(String[] args) {
       int[][] ins = new int[][]{
               {1, 1, 0},
               {1, 1, 0},
               {0, 0, 1},
       };

        _547_省份数量 v = new _547_省份数量();
        System.out.println(v.findCircleNum(ins));
    }

    public int findCircleNum(int[][] isConnected) {
        int len = isConnected.length;
        // 表示那个索引下的身份访问过
        boolean[] visited = new boolean[len];
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                count++;
            }
        }
        return count;
    }

    private void dfs(int[][] isConnected, int index,boolean[] visited) {
        // 表示当前身份被访问过
        visited[index] = true;
        // 遍历相邻的省份
        for (int i = 0; i < isConnected[index].length; i++) {
            if (!visited[i] && isConnected[index][i] == 1) {
                // 没有被访问过，并且有相连的身份
                dfs(isConnected, i, visited);
            }
        }
    }

}
